package xyz.sekai52799.answer.a3001_a3200;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Question3115 {
//    给你一个整数数组 nums。
//
//    返回两个（不一定不同的）质数在 nums 中 下标 的 最大距离。
//
//
//
//    示例 1：
//
//    输入： nums = [4,2,9,5,3]
//
//    输出： 3
//
//    解释： nums[1]、nums[3] 和 nums[4] 是质数。因此答案是 |4 - 1| = 3。
//
//    示例 2：
//
//    输入： nums = [4,8,2,8]
//
//    输出： 0
//
//    解释： nums[2] 是质数。因为只有一个质数，所以答案是 |2 - 2| = 0。
//
//
//
//    提示：
//
//    1 <= nums.length <= 3 * 105
//    1 <= nums[i] <= 100
//    输入保证 nums 中至少有一个质数。

    private Set<Integer> primeNumSet = new HashSet<>();
    public int maximumPrimeDifference(int[] nums) {
        this.initPrimeNumSet();
        int length = nums.length;
        int left = 0;
        int right = length-1;
        for (int i = 0; i < length; i++) {
            if (primeNumSet.contains(nums[i])) {
                left = i;
                break;
            }
        }
        for (int i = length-1; i >= 0 ; i--) {
            if (primeNumSet.contains(nums[i])) {
                right = i;
                break;
            }
        }
        return right - left;
    }

    private void initPrimeNumSet() {
        int num = 100;
        List<Integer> primeNumberList = new ArrayList<>();
        double sqrt = Math.sqrt(num);
        primeNumberList.add(2);
        for (int i = 1;i <= num;i++){
            boolean notPrime = false;
            for (Integer number : primeNumberList){
                if (number > sqrt){
                    break;
                }
                if (i % number == 0 && i != number){
                    notPrime = true;
                    break;
                }
            }
            if (!notPrime && i != 2 && i != 1){
                primeNumberList.add(i);
            }
        }
        this.primeNumSet.addAll(primeNumberList);
    }
}
